package class3;

import common.ListNode;
import common.ListNodeUtils;

/**
 * k个节点的组内逆序调整
 * 问题描述：
 * 给定一个单链表的头节点head,和一个正数K，实现k个节点的小组内部逆序，如果最后一个组不够k就不调整
 * 例子：
 * 调整前：1 ->2 ->3 ->4 ->5 ->6 ->7 ->8，k =3
 * 调整后：3 ->2 ->1 ->6 ->5 ->4 ->7 ->8
 * <p>
 * 解题思路：
 * 1逆序前：a...b -> c...d -> e...f
 * 2.逆序后：b...a -> d...c -> f...e
 * <p>
 * 步骤:
 * 1.分步计数
 */
public class Code06_KGroupReverse {
    public static void main(String[] args) {
        int k = 3;
        int[] arr1 = new int[]{1, 2, 3, 4, 5, 6, 7, 8,9};
        ListNode start = ListNodeUtils.getLinked(arr1);

        ListNode head = kGroupReverse(start, k);
        ListNodeUtils.print(head);
    }

    public static ListNode kGroupReverse(ListNode head, int k) {
        ListNode start = head; // 原start位置
        ListNode end = getHead(start, k);
        if (end == null) {
            return start;
        }
        head = end; // head 为返回的头
        reverseListNode(start, end); // reverse start-end
        ListNode lastEnd = start; // 上一组的结尾节点
        while (lastEnd.next != null) { // 上一组的下一个节点
            start = lastEnd.next;
            end = getHead(start, k);
            if (end == null) {
                return head;
            }
            reverseListNode(start, end);
            lastEnd.next = end;
            lastEnd = start;
        }
        return head;
    }

    public static void reverseListNode(ListNode start, ListNode end) {
        end = end.next;
        ListNode pre = null;
        ListNode next;
        ListNode cur = start;
        while (cur != end) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        start.next = end;
    }

    public static ListNode getHead(ListNode start, int k) {
        while (--k > 0 && start != null) {
            start = start.next;
        }
        return start;
    }

}
